Large deviation principle for enhanced Gaussian processes

We study large deviation principles for Gaussian processes lifted to the free nilpotent group of step N. We apply this to a large class of Gaussian processes lifted to geometric rough paths. A large deviation principle for enhanced (fractional) Brownian motion, in Hölder- or modulus topology, appears as special case.     

Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results

We present anO(p · n) algorithm for the problem of finding disjoint simple paths of minimum total length betweenp given pairs of terminals on oriented partial 2-trees withn nodes and positive or negative arc lengths. The algorithm is inO(n) if all terminals are distinct nodes. We characterize the convex hull of the feasible solution set for the casep=2.We gratefully acknowledge the referee's many helpful suggestions to improve the presentation of this paper.     

Gradient extremals and valley floor bifurcations on potential energy surfaces

Gradient extremals are curves in configuration space denned by the condition that the gradient of the potential energy is an eigenvector of the Hessian matrix. Solutions of a corresponding equation go along a valley floor or along a crest of a ridge, if the norm of the gradient is a minimum, and along a cirque or a cliff or a flank of one of the two if the gradient norm is a maximum. Properties of gradient extremals are discussed for simple 2D model surfaces including the problem of valley bifurcations.     

Reaction paths of some open-shell reactive intermediates

The intermolecular interaction energy for reacting systems in singlet, triplet and doublet states was partitioned by the perturbation expansion method into the chemically meaningful five interaction terms: the Coulomb, exchange-repulsion, induction, dispersion, and charge-transfer energies. In the local ZDO approximation, these energy terms were evaluated for the dimerization of methylenes (^1,3CH₂), the additions of carbenes (^1,3CH₂ and^1,3CF₂) as well as amino radicals (²NH₂ and²NF₂) toward ethylene, and the hydrogen abstractions by methylenes (^1,3CH₂), nitrene (³NH), and hydroxyl radical (²OH) from methane. It has been found that the reaction path is much influenced by the spinmultiplicity, and that the charge-transfer and exchange-repulsion terms play a dominant role in determining the course of reactions.     

Bifurcations and transition states

Bifurcations of reaction channels are related to valley-ridge inflection points and it is examined what happens when these do not coincide with transition states. Under such conditions there result bifurcating regions. There exist a number of different prototypes for such regions which are discussed explicitly on the basis of the pertinent Taylor expansions. When bifurcations occur close enough to transition states then there result bifurcating transition regions. An example for a bifurcating transition region is exhibited which is obtained from a quantum mechanical ab initio calculation for the ring opening of cyclopropylidene to aliene. In general there exist no orthogonal trajectory patterns which could serve as simplified models for channel bifurcations.Operated for the U.S. Department of Energy by Iowa State University under Contract No. W-7405-ENG-82. This work was supported by the Office of Basic Energy Sciences     

An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

A note on packing paths in planar graphs

Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths.Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Seb (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.Research partially supported by the Hungarian National Foundation for Scientific Research Grants OTKA 2118 and 4271.     

Minimum cost multiflows in undirected networks

LetN = (G, T, c, a) be a network, whereG is an undirected graph,T is a distinguished subset of its vertices (calledterminals), and each edgee ofG has nonnegative integer-valuedcapacity c(e) andcost a(e). Theminimum cost maximum multi(commodity)flow problem (*) studied in this paper is to find ac-admissible multiflowf inG such that: (i)f is allowed to contain partial flows connecting any pairs of terminals, (ii) the total value off is as large as possible, and (iii) the total cost off is as small as possible, subject to (ii). This generalizes, on one hand, the undirected version of the classical minimum cost maximum flow problem (when |T| = 2), and, on the other hand, the problem of finding a maximum fractional packing ofT-paths (whena 0). Lovász and Cherkassky independently proved that the latter has a half-integral optimal solution.A pseudo-polynomial algorithm for solving (*) has been developed earlier and, as its consequence, the theorem on the existence of a half-integral optimal solution for (*) was obtained. In the present paper we give a direct, shorter, proof of this theorem. Then we prove the existence of a half-integral optimal solution for the dual problem. Finally, we show that half-integral optimal primal and dual solutions can be designed by a combinatorial strongly polynomial algorithm, provided that some optimal dual solution is known (the latter can be found, in strongly polynomial time, by use of a version of the ellipsoid method).This work was partially supported by Chaire municipale, Mairie de Grenoble, France.     

Exploring potential energy surfaces for chemical reactions: an overview of some practical methods

Potential energy surfaces form a central concept in the application of electronic structure methods to the study of molecular structures, properties, and reactivities. Recent advances in tools for exploring potential energy surfaces are surveyed. Methods for geometry optimization of equilibrium structures, searching for transition states, following reaction paths and ab initio molecular dynamics are discussed. For geometry optimization, topics include methods for large molecules, QM/MM calculations, and simultaneous optimization of the wave function and the geometry. Path optimization methods and dynamics based techniques for transition state searching and reaction path following are outlined. Developments in the calculation of ab initio classical trajectories in the Born-Oppenheimer and Car-Parrinello approaches are described.     

Location of saddle points and minimum energy paths by a constrained simplex optimization procedure

Two methods are proposed, one for the location of saddle points and one for the calculation of steepest-descent paths on multidimensional surfaces. Both methods are based on a constrained simplex optimization technique that avoids the evaluation of gradients or second derivative matrices. Three chemical reactions of increasing structural complexity are studied within the PRDDO SCF approximation. Predicted properties of reaction hypersurfaces are in good overall agreement with those determined by gradient minimization and gradient following algorithms in connection with various ab initio SCF methods. Computational efforts required by the new procedures are discussed.